package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

const Probability = 0.25 // 基于时间与空间综合 best practice 值, 越上层概率越小
const headKey = math.MinInt32
const tailKey  = math.MaxInt32

type node struct {
	up *node
	down *node
	left *node
	right *node
	key int
	value int
}

func newNode(key, value int) *node {
	n := new(node)
	n.key = key
	n.value = value
	return n
}

type skipList struct {
	head  *node
	tail  *node
	level int
	count int
}

func newSkipList() *skipList {
	n := new(skipList)
	n.head = newNode(headKey, 0)
	n.tail = newNode(tailKey, 0)
	n.horizontalLink(n.head, n.tail)
	return n
}

func (sl *skipList) isEmpty() bool {
	return sl.count == 0
}

// 在最下面一层，找到要插入的位置前面的那个key
func (sl *skipList) find(key int) *node {
	curr := sl.head
	for {
		for curr.right.key != tailKey && curr.right.key <= key {
			curr = curr.right
		}

		if curr.down != nil {
			curr = curr.down
		} else {
			break
		}
	}

	return curr
}

func (sl *skipList) search(key int) bool {
	n := sl.find(key)
	return n.key == key
}

func (sl *skipList) put(key int, value int) {
	n := sl.find(key)
	if n.key == key {
		n.value = value
		return
	}

	new := newNode(key, value)
	sl.backLink(n, new)

	currLevel := 0
	for rand.Float32() < Probability {
		if currLevel >= sl.count {
			sl.count++
			p1 := newNode(headKey, 0)
			p2 := newNode(tailKey, 0)
			sl.horizontalLink(p1, p2)
			sl.verticalLink(p1, sl.head)
			sl.verticalLink(p2, sl.tail)
			sl.head = p1
			sl.tail = p2
		}

		for n.up == nil && n.left != nil {
			n = n.left
		}
		n = n.up

		e := newNode(key, 0)
		sl.backLink(n, e)
		sl.horizontalLink(e, n)

		n = e
		currLevel++
	}
	sl.count++
}

// 水平双向连接
func (sl *skipList) horizontalLink(n1 *node, n2 *node) {
	n1.right = n2
	n2.left = n1
}

// 垂直双向连接
func (sl *skipList) verticalLink(n1 *node, n2 *node) {
	n1.down = n2
	n2.up = n1
}

func (sl *skipList) backLink(n1 *node, n2 *node) {
	n2.left = n1
	n2.right = n1.right
	n1.right.left = n2
	n1.right = n2
}

func (sl *skipList) print() {

	curr := sl.head
	level := 0
	for curr != nil {
		n := curr
		for n != nil {
			fmt.Printf("%d ", n.key)
			n = n.right
		}

		fmt.Printf("***************** Level %d \n", level + 1)
		fmt.Println()
		curr = curr.down
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())

	list := newSkipList()
	for i := 0; i < 20; i++ {
		list.put(i, i)
	}
	list.print()
}

//func randLevel() (level int) {
//
//	for level = 1; rand.Float32() < Probability && level < MaxLevel; level++ {
//		// fmt.Println(rand.Float32())
//	}
//	// fmt.Printf("up to %d level\n", level)
//	return
//}
//
//type node struct {
//	forward []*node
//	key     int
//}
//
//type skipList struct {
//	head  *node
//	level int
//}
//
//func newNode(key, level int) *node {
//	return &node{key: key, forward: make([]*node, level)}
//}
//
//func newSkipList() *skipList {
//	return &skipList{head: newNode(0, MaxLevel), level: 1}
//}
//
//func (s *skipList) insert(key int) {
//	current := s.head
//	update := make([]*node, MaxLevel) // 新节点插入以后的前驱节点
//	for i := s.level - 1; i >= 0; i-- {
//		if current.forward[i] == nil {
//			update[i] = current
//		} else {
//			for current.forward[i] != nil && current.forward[i].key < key {
//				current = current.forward[i] // 指针往前推进
//			}
//			update[i] = current
//		}
//	}
//
//	level := randLevel()
//	if level > s.level {
//		// 新节点层数大于跳表当前层数时候, 现有层数 + 1 的 head 指向新节点
//		for i := s.level; i < level; i++ {
//			update[i] = s.head
//		}
//		s.level = level
//	}
//	node := newNode(key, level)
//	for i := 0; i < level; i++ {
//		node.forward[i] = update[i].forward[i]
//		update[i].forward[i] = node
//	}
//}
//
//func (s *skipList) delete(key int) {
//	current := s.head
//	for i := s.level - 1; i >= 0; i-- {
//		for current.forward[i] != nil {
//			if current.forward[i].key == key {
//				tmp := current.forward[i]
//				current.forward[i] = tmp.forward[i]
//				tmp.forward[i] = nil
//			} else if current.forward[i].key > key {
//				break
//			} else {
//				current = current.forward[i]
//			}
//		}
//	}
//
//}
//
//func (s *skipList) search(key int) *node {
//	// 类似 delete
//	return nil
//}
//
//func (s *skipList) print() {
//	fmt.Println()
//
//	for i := s.level - 1; i >= 0; i-- {
//		current := s.head
//		for current.forward[i] != nil {
//			fmt.Printf("%d ", current.forward[i].key)
//			current = current.forward[i]
//		}
//		fmt.Printf("***************** Level %d \n", i+1)
//	}
//}
//
//func main() {
//
//	rand.Seed(time.Now().UnixNano())
//
//	list := newSkipList()
//	for i := 0; i < 20; i++ {
//		list.insert(i)
//	}
//	list.print()
//
//	fmt.Println("\n--------------------------------------")
//
//	//list.delete(10)
//	//list.print()
//	//
//	//fmt.Println("\n--------------------------------------")
//}